package com.zjsru.plan2023.oneday.oneDay202303;

/**
 * @Author: CookLee
 * @Date: 2023/4/22
 * 最长等差数列
 *
 * 输入：nums = [3,6,9,12]
 * 输出：4
 * 解释：
 * 整个数组是公差为 3 的等差数列。
 *
 * 输入：nums = [9,4,7,2,10]
 * 输出：3
 * 解释：
 * 最长的等差子序列是 [4,7,10]。
 *
 *
 * 提示：
 *
 * 2 <= nums.length <= 1000
 * 0 <= nums[i] <= 500
 */
public class LongestArithSeqLength {
    
    /**
     * 最长算术seq长度
     *
     * @param nums
     * @return int
     */
    public int longestArithSeqLength(int[] nums) {
        int len = nums.length;
        int ans = 0;
        int[][] f = new int[len][1001];
        //要求是连续的最大公差值 遍历
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                // 按照要求：由于公差可能为负数，且最大差值为 500，因此，我们可以将统一将公差加上 500，这样公差的范围就变成了 [0,1000] 。
                int k = nums[i] - nums[j] + 500;
                //f[j][k] 标记每次前后数相减时计数，起始值为0，遇到相同的+1； f[i][k] 表示该轮遍历计数后的总值
                f[i][k] = Math.max(f[i][k],f[j][k] + 1);
                ans = Math.max(ans,f[i][k]);
            }
        }
        return ans  + 1;
    
    }
    
    public static void main(String[] args) {
        LongestArithSeqLength longestArithSeqLength = new LongestArithSeqLength();
        int[] nums = new int[] {3, 6, 9, 12};
        System.out.println(longestArithSeqLength.longestArithSeqLength(nums));
    }
}
